在Java中排序 |
您所在的位置：网站首页 › java sort排序comparator › 在Java中排序 |
|
1.概述
本文将说明如何在Java 7和Java 8中对Array、List、Set和Map应用排序。 2.用Array进行排序让我们先用Arrays.sort() 方法来对整数数组进行排序。 我们将在一个@BeforejUnit方法中定义以下int数组。 @Before public void initVariables () { toSort = new int[] { 5, 1, 89, 255, 7, 88, 200, 123, 66 }; sortedInts = new int[] {1, 5, 7, 66, 88, 89, 123, 200, 255}; sortedRangeInts = new int[] {5, 1, 89, 7, 88, 200, 255, 123, 66}; ... } 2.1.对完整数组进行排序现在让我们来使用简单的Array.sort() API。 @Test public void givenIntArray_whenUsingSort_thenSortedArray() { Arrays.sort(toSort); assertTrue(Arrays.equals(toSort, sortedInts)); }未排序的数组现在已经完全排序了。 [1, 5, 7, 66, 88, 89, 123, 200, 255]如官方 JavaDoc 中所述，Arrays.sort 在基元 上使用双枢轴快速排序。它提供 O(n log(n)) 性能，通常比传统（单轴）快速排序实现更快。但是，它使用 对象数组的合并排序算法。 2.2.对数组的一部分进行排序Arrays.sort还有一个sort APIs – 我们将在这里讨论这个问题。 Arrays.sort(int[] a, int fromIndex, int toIndex)这将只对数组的一部分进行排序，即在两个索引之间进行排序。 让我们看一下一个快速的例子。 @Test public void givenIntArray_whenUsingRangeSort_thenRangeSortedArray() { Arrays.sort(toSort, 3, 7); assertTrue(Arrays.equals(toSort, sortedRangeInts)); }排序将只在下面的子数组元素上进行（toIndex将是排他性的）。 [255, 7, 88, 200]结果排序后的子数组与主数组包括在一起，将是。 [5, 1, 89, 7, 88, 200, 255, 123, 66] 2.3 Java 8 Arrays.sort 与Arrays.parallelSort的对比Java 8带有一个新的API – parallelSort – 具有与Arrays.sort() API类似的签名。 @Test public void givenIntArray_whenUsingParallelSort_thenArraySorted() { Arrays.parallelSort(toSort); assertTrue(Arrays.equals(toSort, sortedInts)); }在parallelSort()的背后，它把数组分成不同的子数组（按照parallelSort算法的粒度）。每个子数组在不同的线程中用Arrays.sort()进行排序，这样sort可以以并行的方式执行，最后合并为一个排序的数组。 请注意，ForJoin公共池被用来执行这些并行任务，然后合并结果。 当然，Arrays.parallelSort的结果要和Array.sort一样，只是利用了多线程的问题。 最后，在Arrays.parallelSort中也有类似的API Arrays.sort的变体。 Arrays.parallelSort (int [] a, int fromIndex, int toIndex); 3.对一个List进行排序现在让我们使用Collections.sort()API中的java.utils.Collections – 来对一个List的整数进行排序。 @Test public void givenList_whenUsingSort_thenSortedList() { List toSortList = Ints.asList(toSort); Collections.sort(toSortList); assertTrue(Arrays.equals(toSortList.toArray(), ArrayUtils.toObject(sortedInts))); }排序前的List将包含以下元素： [5, 1, 89, 255, 7, 88, 200, 123, 66]自然地，排序后： [1, 5, 7, 66, 88, 89, 123, 200, 255]正如Oracle JavaDoc中提到的Collections.Sort，它使用了修改过的mergesort，并提供了有保证的n log(n)性能。 4.对一个Set集进行排序接下来，让我们使用Collections.sort()来对一个LinkedHashSet进行排序。 我们使用LinkedHashSet，因为它可以保持插入顺序。 请注意，为了在Collections中使用sort API – 我们首先将集合包裹在一个列表中。 @Test public void givenSet_whenUsingSort_thenSortedSet() { Set integersSet = new LinkedHashSet(Ints.asList(toSort)); Set descSortedIntegersSet = new LinkedHashSet( Arrays.asList(new Integer[] {255, 200, 123, 89, 88, 66, 7, 5, 1})); List list = new ArrayList(integersSet); Collections.sort(Comparator.reverseOrder()); integersSet = new LinkedHashSet(list); assertTrue(Arrays.equals( integersSet.toArray(), descSortedIntegersSet.toArray())); }Comparator.reverseOrder() 方法将自然排序所强加的排序颠倒过来。 5.排序Map在本节中，我们将开始研究对 Map 进行排序——既可以按键也可以按值。 让我们首先定义一下我们要排序的Map。 @Before public void initVariables () { .... HashMap map = new HashMap(); map.put(55, "John"); map.put(22, "Apple"); map.put(66, "Earl"); map.put(77, "Pearl"); map.put(12, "George"); map.put(6, "Rocky"); .... } 5.1 按键对Map进行排序我们现在要从HashMap中提取keys和values条目，并根据本例中的键值对其进行排序。 @Test public void givenMap_whenSortingByKeys_thenSortedMap() { Integer[] sortedKeys = new Integer[] { 6, 12, 22, 55, 66, 77 }; List entries = new ArrayList(map.entrySet()); Collections.sort(entries, new Comparator() { @Override public int compare( Entry o1, Entry o2) { return o1.getKey().compareTo(o2.getKey()); } }); Map sortedMap = new LinkedHashMap(); for (Map.Entry entry : entries) { sortedMap.put(entry.getKey(), entry.getValue()); } assertTrue(Arrays.equals(sortedMap.keySet().toArray(), sortedKeys)); }请注意我们在复制基于键的排序条目时如何使用LinkedHashMap （因为HashSet不保证键的顺序）。 排序前的Map： [Key: 66 , Value: Earl] [Key: 22 , Value: Apple] [Key: 6 , Value: Rocky] [Key: 55 , Value: John] [Key: 12 , Value: George] [Key: 77 , Value: Pearl]按键排序后的Map： [Key: 6 , Value: Rocky] [Key: 12 , Value: George] [Key: 22 , Value: Apple] [Key: 55 , Value: John] [Key: 66 , Value: Earl] [Key: 77 , Value: Pearl] 5.2.按照值对Map进行排序这里我们将比较HashMap的值，以根据HashMap的值进行排序： @Test public void givenMap_whenSortingByValues_thenSortedMap() { String[] sortedValues = new String[] { "Apple", "Earl", "George", "John", "Pearl", "Rocky" }; List entries = new ArrayList(map.entrySet()); Collections.sort(entries, new Comparator() { @Override public int compare( Entry o1, Entry o2) { return o1.getValue().compareTo(o2.getValue()); } }); Map sortedMap = new LinkedHashMap(); for (Map.Entry entry : entries) { sortedMap.put(entry.getKey(), entry.getValue()); } assertTrue(Arrays.equals(sortedMap.values().toArray(), sortedValues)); }排序前的Map： [Key: 66 , Value: Earl] [Key: 22 , Value: Apple] [Key: 6 , Value: Rocky] [Key: 55 , Value: John] [Key: 12 , Value: George] [Key: 77 , Value: Pearl]按值排序后的Map： [Key: 22 , Value: Apple] [Key: 66 , Value: Earl] [Key: 12 , Value: George] [Key: 55 , Value: John] [Key: 77 , Value: Pearl] [Key: 6 , Value: Rocky] 6.对自定义对象进行排序现在让我们使用自定义对象： public class Employee implements Comparable { private String name; private int age; private double salary; public Employee(String name, int age, double salary) { ... } // standard getters, setters and toString }在下面的章节中，我们将使用下面的Employee数组来进行排序的例子： @Before public void initVariables () { .... employees = new Employee[] { new Employee("John", 23, 5000), new Employee("Steve", 26, 6000), new Employee("Frank", 33, 7000), new Employee("Earl", 43, 10000), new Employee("Jessica", 23, 4000), new Employee("Pearl", 33, 6000)}; employeesSorted = new Employee[] { new Employee("Earl", 43, 10000), new Employee("Frank", 33, 70000), new Employee("Jessica", 23, 4000), new Employee("John", 23, 5000), new Employee("Pearl", 33, 4000), new Employee("Steve", 26, 6000)}; employeesSortedByAge = new Employee[] { new Employee("John", 23, 5000), new Employee("Jessica", 23, 4000), new Employee("Steve", 26, 6000), new Employee("Frank", 33, 70000), new Employee("Pearl", 33, 4000), new Employee("Earl", 43, 10000)}; }我们也可以对数组或自定义对象的集合进行排序。 按照自然顺序（使用Comparable接口）或 按照Comparator接口提供的顺序进行 6.1.使用Comparablejava中的自然顺序是指在一个给定的数组或集合中，基元或对象应该被有序地排序的一个顺序。 java.util.Arrays 和java.util.Collections 都有一个sort()方法，强烈建议自然顺序应与equals的语义相一致。 在这个例子中，我们将把具有相同name的员工视为平等的。 @Test public void givenEmpArray_SortEmpArray_thenSortedArrayinNaturalOrder() { Arrays.sort(employees); assertTrue(Arrays.equals(employees, employeesSorted)); }你可以通过实现一个Comparable 接口来定义元素的自然顺序，该接口有compareTo()方法，用于比较当前对象和作为参数传递的对象。 为了清楚地理解这一点，让我们看看一个实现了Comparable Interface的Employee类的例子。 public class Employee implements Comparable { ... @Override public boolean equals(Object obj) { return ((Employee) obj).getName().equals(getName()); } @Override public int compareTo(Object o) { Employee e = (Employee) o; return getName().compareTo(e.getName()); } }一般来说，比较的逻辑将被写入方法compareTo。这里我们要比较雇员的顺序或雇员字段的name。如果两个雇员有相同的名字，他们将是相等的。 现在，当Arrays.sort(employees);在上述代码中被调用时，我们现在知道了根据name对雇员进行排序的逻辑和顺序。 [("Earl", 43, 10000),("Frank", 33, 70000), ("Jessica", 23, 4000), ("John", 23, 5000),("Pearl", 33, 4000), ("Steve", 26, 6000)]我们可以看到数组是按雇员的名字排序的 – 这现在成为Employee类的自然顺序。 6.2.使用Comparator现在，让我们使用Comparator接口实现对元素进行排序 – 在这里，我们将匿名的内部类即时传递给Arrays.sort()API。 @Test public void givenIntegerArray_whenUsingSort_thenSortedArray() { Integer [] integers = ArrayUtils.toObject(toSort); Arrays.sort(integers, new Comparator() { @Override public int compare(Integer a, Integer b) { return Integer.compare(a, b); } }); assertTrue(Arrays.equals(integers, ArrayUtils.toObject(sortedInts))); }现在让我们根据salary – 对雇员进行排序，并传入另一个比较器的实现。 Arrays.sort(employees, new Comparator() { @Override public int compare(Employee o1, Employee o2) { return Double.compare(o1.getSalary(), o2.getSalary()); } });基于salary的排序的Employees数组将是： [(Jessica,23,4000.0), (John,23,5000.0), (Pearl,33,6000.0), (Steve,26,6000.0), (Frank,33,7000.0), (Earl,43,10000.0)]注意，我们可以用Collections.sort()以类似的方式对List和Set的对象按自然或自定义顺序进行排序，就像上面对数组所描述的那样。 7.用Lambdas进行排序从Java 8开始，我们可以使用Lambdas来实现Comparator功能接口。 您可以看看Java 8中的Lambdas写的内容，以了解语法。 让我们替换掉旧的比较器吧： Comparator c = new Comparator() { @Override public int compare(Integer a, Integer b) { return Integer.compare(a, b); } }与之等价的实现，使用Lambda表达式： Comparator c = (a, b) -> Integer.compare(a, b);最后，我们来写一下测试： @Test public void givenArray_whenUsingSortWithLambdas_thenSortedArray() { Integer [] integersToSort = ArrayUtils.toObject(toSort); Arrays.sort(integersToSort, (a, b) -> { return Integer.compare(a, b); }); assertTrue(Arrays.equals(integersToSort, ArrayUtils.toObject(sortedInts))); }正如你所看到的，这里的逻辑更干净、更简明。 8.使用Comparator.comparing和Comparator.thenComparingJava 8 带有两个对排序有用的新 API – Comparator接口中的comparing() 和thenComparing() 。 这些对于链接Comparator的多个条件非常方便。 让我们考虑这样一种情况：我们可能想通过员工与年龄进行比较，然后再通过姓名进行比较。 @Test public void givenArrayObjects_whenUsingComparing_thenSortedArrayObjects() { List employeesList = Arrays.asList(employees); employees.sort(Comparator.comparing(Employee::getAge)); assertTrue(Arrays.toString(employees.toArray()) .equals(sortedArrayString)); }在这个例子中，Employee::getAge是Comparator接口的排序键，实现了一个具有比较功能的接口。 下面是排序后的Employees数组。 [(John,23,5000.0), (Jessica,23,4000.0), (Steve,26,6000.0), (Frank,33,7000.0), (Pearl,33,6000.0), (Earl,43,10000.0)]这里的雇员是根据年龄来排序的。 我们可以看到John和Jessica年龄相同–；这意味着现在的顺序逻辑应该考虑到他们的名字--我们可以用thenComparing()来实现。 ... employees.sort(Comparator.comparing(Employee::getAge) .thenComparing(Employee::getName)); ...用上述代码片段进行排序后，雇员数组中的元素将被排序为： [(Jessica,23,4000.0), (John,23,5000.0), (Steve,26,6000.0), (Frank,33,7000.0), (Pearl,33,6000.0), (Earl,43,10000.0) ]因此 comparing() 和thenComparing()肯定会使更复杂的排序场景的实现变得更干净。 9.结语在这篇文章中，我们看到了如何将排序应用于Array、List、Set和Map。 我们还看到了关于Java 8的功能如何在排序中发挥作用的简要介绍，如Lambdas的使用、comparing()和thenComparing()以及parallelSort()等。 文章中使用的所有例子都可以在GitHub上找到。 |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |